# -*- coding: utf-8 -*-
"""
@Time ： 2022/7/28 15:01
@Auth ： Mr. William 1052949192
@Company ：特斯汀学院 @testingedu.com.cn
@Function ：面向对象的封装
"""
from class6.homework.decs import my_time_new


class MySort:

    @my_time_new()
    def bub_sort(self, height):
        """
        冒泡排序
        :param height: 待排序列表
        """
        # 因为列表剩最后一个元素的时候，也不用比了
        for j in range(len(height) - 1):
            # 实现第一轮：两两比较，冒出最大的
            # 因为最后一个不用比，它没有后一个了
            # 每一轮比较都有一个元素不用再比了
            for i in range(0, len(height) - 1 - j):
                # 前一个和后一个比
                if height[i] < height[i + 1]:
                    height[i], height[i + 1] = height[i + 1], height[i]

    @my_time_new()
    def select_sort(self, height):
        """
        选择排序
        :param height:待排序列表
        """
        # 剩下一个元素就不用比较了
        for j in range(len(height) - 1):
            # 找到最大的，记录下标
            max_index = 0
            # 每一轮要少比一个
            for i in range(1, len(height) - j):
                # 如果当前元素比最大值大，就记录当前元素下标
                if height[i] < height[max_index]:
                    max_index = i

            # print(max_index)
            # 交换到末尾
            # 最后一个元素下标也要-j
            height[max_index], height[len(height) - 1 - j] = height[len(height) - 1 - j], height[max_index]

    def quicksort(self, height, left, right):
        """
        快速排序的函数
        :param height: 列表
        :param left: 列表的左边
        :param right: 待排序列表的右边
        """
        # 取最右边为基准
        base = height[right]
        # 指针初始位置
        l = left
        h = right

        while l < h:
            # 一轮交换
            # 只要l还在h的左边，就一直循环
            while l < h:
                # 从左往右找到比基准大的
                if height[l] > base:
                    # 交换到h位置
                    height[l], height[h] = height[h], height[l]
                    h -= 1
                    break
                else:
                    # 如果没找到就继续找
                    l += 1

            while l < h:
                # 从右往左找比基准小的
                if height[h] < base:
                    # 交换到l位置
                    height[l], height[h] = height[h], height[l]
                    l += 1
                    break
                else:
                    # 如果没找到就继续找
                    h -= 1

        # 递归调用直达，所有部分都只剩下一个或者0个元素
        if l - 1 - left > 0:
            # 对左边剩下的元素进行递归
            self.quicksort(height, left, l - 1)

        if right - h - 1 > 0:
            # 对右边剩下的元素进行递归
            self.quicksort(height, h + 1, right)


if __name__ == '__main__':
    # 创建对象
    mysort = MySort()

    # 由升序排成降序
    h = [i for i in range(2000)]
    mysort.bub_sort(h)

    # 由升序排成降序
    h = [i for i in range(2000)]
    mysort.select_sort(h)

    # 修改默认堆栈大小
    import sys,time
    sys.setrecursionlimit(10000000)
    t1 = time.time()
    h = [i for i in range(2000, 0, -1)]
    mysort.quicksort(h, 0, len(h) - 1)
    t2 = time.time()
    print('快排：', round((t2 - t1) * 1000, 2), 'ms')